package zuo.test5_binaryTree;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @Author: Forx
 * @Data: 2021/6/14
 * @Desc: Algorithm - zuo.test5_binaryTree
 * @Version: v1.0
 */

class Node<V>{
    V val;
    Node left;
    Node right;

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}
class NodeI{
    int val;
    NodeI left;
    NodeI right;

    public NodeI(int val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                ", left=" + left +
                ", right=" + right +
                '}';
    }
}
class NodeS{
    int val;
    NodeS left;
    NodeS right;
    NodeS parent;
    @Override
    public String toString() {
        return "Node{" +
                "val=" + val +
                ", left=" + left +
                ", right=" + right +
                ",parent=" + parent+
                '}';
    }
}

public class binaryTree {
    public static void Inorder(Node tree){
        if(tree!=null){
            Inorder(tree.left);
            System.out.println(tree);
            Inorder(tree.right);
        }
    }
    public static void Preorder(Node tree){
        if(tree!=null){
            System.out.println(tree);
            Preorder(tree.left);
            Preorder(tree.right);
        }

    }
    public static void Lastorder(Node tree){
        if(tree!=null){
            Inorder(tree.left);

            Inorder(tree.right);
            System.out.println(tree);
        }

    }
    public static void PreOrderUnRecur(Node tree){
        Node head = tree;
        if(tree!=null){
            Stack<Node> s = new Stack<>();
            s.add(tree);
            while (!s.empty()){
                head = s.pop();
                System.out.println("head = " + head);
                if(head.right!=null){
                    s.push(head.right);
                }
                if(head.left!=null){
                    s.push(head.left);
                }
            }
        }

    }
    public static void InorderUnRecur(Node tree){
        Node head = tree;
        if(tree!=null){
            Stack<Node> s = new Stack<>();
            while (!s.empty() || head!=null){
                if(head!=null){
                    s.push(head);
                    head = head.left;
                }else {
                    head = s.pop();
                    System.out.println("head = " + head);
                    head = head.right;
                }
            }
        }
    }
    /**
     * 把前序遍历的顺序反过来
     * */
    public static void PosOrderUnRecur(Node tree){
        Node head = tree;
        if(tree!=null){
            Stack<Node> s = new Stack<>();
            Stack<Node> s2 = new Stack<>();
            s.push(tree);
            while (!s.empty()){
                head = s.pop();
                s2.push(head);
                //System.out.println("head = " + head);
                if(head.left!=null){
                    s.push(head.left);
                }
                if(head.right!=null){
                    s.push(head.right);
                }

            }
            while (!s2.isEmpty()){
                System.out.println(s2.pop());
            }
        }
    }
    /**
     * 层序遍历
     * */
    public static void widthOrder(Node tree){
        if (tree==null)return;
        Queue<Node> queue = new LinkedList<>();
        HashMap<Node,Integer> levelMap = new HashMap<>();
        levelMap.put(tree,1);
        int curLevel = 1;
        int curLevelNodes = 0;
        int maxWidth = Integer.MIN_VALUE;
        queue.add(tree);
        Node head = null;
        while (!queue.isEmpty()){
            head = queue.poll();
            int curNodeLevel = levelMap.get(head);
            if(curNodeLevel == curLevel){
                curLevelNodes++;
            }else {
                maxWidth = Math.max(maxWidth,curLevelNodes);
                curLevel++;
                curLevelNodes = 0;
            }
            if(head.left!=null){
                levelMap.put(head.left,curNodeLevel+1);
                queue.add(head.left);

            }
            if(head.right!=null){
                queue.add(head.right);
                levelMap.put(head.right,curNodeLevel+1);
            }
        }

    }

    /**
     * 二叉树的相关概念及其实现判断
     * 如何判断一颗二叉树是否是搜索二叉树？   中序遍历从小到大
     * 如何判断一颗二叉树是完全二叉树？       层次遍历-{1.遍历过程中若遇到有右无左直接返回FALSE 2.若遇到一个不是同时拥有左右孩子的节点,则在他之后的节点必须都是叶子节点}
     * 如何判断一颗二叉树是否是满二叉树？     节点数和高的关系
     * 如何判断一颗二叉树是否是平衡二叉树？(二叉树题目套路）  判断左右树高度之差
     * 给定节点n1和n2,找最近公共节点          后序遍历
     * */
    public static class bstInfo{
        int min;
        int max;
        boolean isBst;

        public bstInfo(int min, int max, boolean isBst) {
            this.min = min;
            this.max = max;
            this.isBst = isBst;
        }

        @Override
        public String toString() {
            return "bstInfo{" +
                    "min=" + min +
                    ", max=" + max +
                    ", isBst=" + isBst +
                    '}';
        }
    }

    public static bstInfo isBST(NodeI head){
        if(head==null){
            return null;
        }
        bstInfo leftInfo = isBST(head.left);
        bstInfo rightInfo = isBST(head.right);
        int min = head.val;
        int max = head.val;

        if(leftInfo!=null){

            if(!leftInfo.isBst || max < leftInfo.max)return new bstInfo(min,max,false);

            min = Math.min(min,leftInfo.min);
            max = Math.max(max,leftInfo.max);
        }
        if(rightInfo!=null){
            if(!rightInfo.isBst || min > rightInfo.min)return new bstInfo(min,max,false);
            min = Math.min(min,rightInfo.min);
            max = Math.max(max,rightInfo.max);
        }
        return new bstInfo(min,max,true);
    }


    public static Node lowerAncestor(Node head,Node n1,Node n2){
        if (head==null || head == n1 || head ==n2){
            return head;
        }
        Node left = lowerAncestor(head.left,n1,n2);//向左树要n1
        Node right = lowerAncestor(head.right,n1,n2);
        if(left!=null&&right!=null)return head;
        return left!=null?left:right;
    }

    /**
     * 在二叉树中找到一个节点的后继节点
     * 【题目】现在有一种新的二叉树节点类型如下：
     * public class Node {
     * public int value;
     * public Node left;
     * public Node right;
     * public Node parent;
     * public Node(int val){
     *        value = val;
     *        }
     * }
     * 该结构比普通二叉树节点结构多了一个指向父节点的parent指针。
     * 假设有一棵Node类型的节点组成的二叉树，树中每个节点的parent指针都正确地指向自己的父节点，头节
     * 点的parent指向null。
     * 只给一个在二叉树中的某个节点node,请实现返回node的后继节点的函数。
     * 在二叉树的中序遍历的序列中，node的下一个节点叫作node的后继节点。
     *
     * 假如求X的后继节点
     * 有两种情况   1.X有右子树,则是右子树的最左节点   2.无右子树,则向上走,若自己不是父节点
     * 的左孩子,则从父节点继续向上走,直到是父节点的左孩子,则此时X的后继节点就是这个父节点
     *              a --- 发现b是a的左孩子,停止,x的后继是a
     *             /
     *            b --- 发现d不是b的做孩子,向上走
     *             \
     *              d --- 发现x不是d的左孩子,向上走
     *               \
     *                x
     *
     *
     * */

    public static NodeS getSuccessorNode(NodeS head){
        if (head == null)return null;
        if(head.right!=null){
            //得到最左
            NodeS cur = head.right;
            while (cur.left!=null){
                cur = cur.left;
            }
            return cur;
        }else {
            //往上找
            NodeS cur = head;
            while (cur.parent!=null && cur.parent.left!=cur){
                cur = cur.parent;
            }
            return cur.parent;
        }
    }
    /**
     * 二叉树的序列化和反序列化
     * 就是内存里的一棵树如何变成字符串形式，又如何从字符串形式变成内存里的树
     *  序列化->用特殊字符做标记例如用_代表一个节点的结束#代表空字符串
     *  反序列化
     * 如何判断一颗二叉树是不是另一棵二叉树的子树？
     * */
    public static String treeToStr(NodeI head){
        if(head==null){
            return "#_";
        }
        String res = head.val + "_";
        res+=treeToStr(head.left);
        res+=treeToStr(head.right);
        return res;
    }
    public static NodeI strToTreeRecu(Queue queue){
        String value = (String) queue.poll();
        if("#".compareTo(value) == 0){
            return null;
        }
        NodeI head = new NodeI(Integer.valueOf(value));
        head.left = strToTreeRecu(queue);
        head.right = strToTreeRecu(queue);
        return head;

    }
    public static NodeI strToTree(String string){
        String[] values = string.split("_");
        Queue<String> queue = new LinkedList<>();
        for(String str:values){
            queue.add(str);
        }
        return strToTreeRecu(queue);
    }

    /**
     * 折纸 >是凹的<是凸的
     * n(折纸次数)   1  2   3
     *              |   |   >
     *              |   >   >
     *              |   |   <
     *              |   |   |
     *              >   >   >
     *              |   |   >
     *              |   <   <
     *              |   |   <
     * 要求 输入n 输出凹凸序列
     *
     *  将此看做一个二叉树可有
     *       >
     *     /  \
     *    >   <
     *   /\   /\
     *  >  < >  <
     *
     *  任一个节点的子节点都是左凹右凸
     *  然后先序遍历既是结果
     *
     * */
    public static void getAoTuProcess(int n,char[] ans,int left,int right,boolean flag){
        if(n<=0)return;
        int mid = left+(right-left)/2;
        if(flag)ans[mid] = 'a';
        else ans[mid] = 't';
        getAoTuProcess(n-1,ans,left,mid-1,true);
        getAoTuProcess(n-1,ans,mid+1,right,false);
    }
    public static void getAoTu(int n){
        char[] res = new char[(1<<n)-1];
        getAoTuProcess(n,res,0,res.length-1,true);
    }

    public static void printTree(NodeI head) {
        System.out.println("Binary Tree:");
        printInOrder(head, 0, "H", 17);
        System.out.println();
    }

    public static void printInOrder(NodeI head, int height, String to, int len){
        if (head == null) {
            return;
        }
        printInOrder(head.right, height + 1, "v", len); // 递归遍历右子树
        String val = to + head.val + to; // 处理并打印根节点
        int lenM = val.length();
        int lenL = (len - lenM) / 2;
        int lenR = len - lenM - lenL;
        val = getSpace(lenL) + val + getSpace(lenR);
        System.out.println(getSpace(height * len) + val);
        printInOrder(head.left, height + 1, "^", len); // 递归遍历左子树
    }

    public static String getSpace(int num) {
        String space = " ";
        StringBuffer buf = new StringBuffer("");
        for (int i = 0; i < num; i++) {
            buf.append(space);
        }
        return buf.toString();
    }

    public static void main(String[] args) {
        getAoTu(3);

        String treeStr = "1_2_#_4_#_#_3_5_7_#_#_#_6_#_#_";
        NodeI head = strToTree(treeStr);//可以的通过字符串来构建二叉树
        printTree(head);
        System.out.println(treeToStr(head));
        System.out.println(isBST(head));

    }
}
